12324 - Philip J. Fry Problem/zubieta.cpp

   1 #include <iostream>
   2 #include <cmath>
   3 #include <vector>
   4 #include <map>
   5 #include <stack>
   6 #include <queue>
   7 #include <deque>
   8 #include <sstream>
   9 #include <list>
  10 #include <set>
  11 #include <algorithm>
  12 #include <stdio.h>
  13 #include <stdlib.h>
  14
  15 using namespace std;
  16
  17 int n;
  18 int viajes[105];
  19 int bolas[105];
  20 int mat[105][105*105];
  21
  22 int func(int a, int b, bool c){
  23         if(mat[a][b])
  24                 return mat[a][b];
  25
  26         int thisTravel = viajes[a]/(c?2:1);
  27         b += bolas[a];
  28         if(a!=n-1)
  29                 if(b)
  30                         mat[a][b] = (thisTravel += min(func(a+1,b-1,1),func(a+1,b,0)));
  31                 else
  32                         mat[a][b] = (thisTravel += func(a+1,b,0));
  33
  34         return thisTravel;
  35 }
  36
  37 int main(){
  38         scanf("%d",&n);
  39         while(true){
  40                 if(!n){
  41                         break;
  42                 }
  43                 for(int z=0;z<n;++z){
  44                         scanf("%d",&viajes[z]);
  45                         scanf("%d",&bolas[z]);
  46                 }
  47                 for(int z=0;z<n;++z)
  48                         for(int y=0;y<n*n;++y)
  49                                 mat[z][y]=0;
  50                 printf("%d\n",func(0,0,0));
  51                 scanf("%d",&n);
  52         }
  53 }